package com.xiaozhameng.study.algorithm.heap;

/**
 * 堆数据结构的实现
 */
public class Heap {
    /**
     * 数组，从下标1开始存储数据
     */
    private int n;
    /**
     * 堆可以存储的最大数据个数
     */
    private int[] a;
    /**
     * 堆中已经存储的数据个数
     */
    private int count;

    /**
     * 堆结构
     * @param capacity 容量
     */
    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    /**
     * 堆化
     *
     * @param data 新增的元素
     */
    public void insert(int data) {
        if (count >= n) {
            return; // 堆满了
        }
        ++count;
        a[count] = data;
        int i = count;
        // 自下往上堆化
        while (i / 2 > 0 && a[i] > a[i / 2]) {
            // swap()函数作用：交换下标为i和i/2的两个元素
            swap(a, i, i / 2);
            i = i / 2;
        }
    }

    /**
     * 交换两个元素的
     */
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}